package MCM;

public class dynamicProgramming {
	int n;
    int[][] m;
    int[][] s;
    int[] p;
    final int MAX = Integer.MAX_VALUE;
    
    dynamicProgramming(int n,int[][] m,int[][] s,int[] p){
    	this.n = n;
    	this.m = m;
    	this.s = s;
    	this.p = p;
    }
    
    //三重循环实现
    public void run() {
    	for (int l = 2; l <= n; l++)
        {
            for (int i = 1; i <= n - l + 1; i++)
            {
                int j = i + l - 1;
                m[i][j] = MAX;
                for (int k = i; k <= j - 1; k++)
                {
                    int q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
                    if (q < m[i][j])
                    {
                        m[i][j] = q;
                        s[i][j] = k;
                        printM();
                    }
                }
            }
        }
    }
    
    //递归实现
    public int runOther(int left,int right) {
    	if(left == right)
    		return 0;
    	if(m[left][right] > 0)
    		return m[left][right];
    	int num = MAX;
        for(int i=left;i<right;i++)
        {
            num=Math.min(num,runOther(left,i) + runOther(i+1,right) + p[left-1]*p[i]*p[right]);
            s[left][right]=i;  //记录最佳分解方案时i的值
            printM();
        }
        m[left][right]=num;
        return num;
    }
    
    public void printM() {
    	for (int i = 0; i < s.length; i++) {
            for (int j = 0; j < s[i].length; j++) {
                    System.out.print(s[i][j] + " ");
            }
            System.out.println();
	    }
        System.out.println();
        System.out.println();
    }
}
